class Solution {
public:
    int strStr(string haystack, string needle) {
        string str=needle+'#'+haystack;
        vector<int> pi(str.size());
        for(int i=1;i<str.size();i++)
        {
            int len=pi[i-1];
            while(len && str[i]!=str[len])
            {
                len=pi[len-1];
            }
            if(str[len]==str[i])
            {
                pi[i]=len+1;
                if(pi[i]==needle.size())
                {
                    return i-2*needle.size();
                }
            }
        }
        return -1;
    }
};